package com.jia.interviewPro;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * @program: Leetcode
 * @description:  https://leetcode-cn.com/problems/sparse-array-search-lcci/
 * @author: STU756
 * @create: 2020-09-03 11:20
 */
public class Pro1005 {
    static class Word implements Comparable<Word>{
        String w;
        int index;
        public Word(String w, int index) {
            this.w = w;
            this.index = index;
        }

        @Override
        public int compareTo(Word o) {
            return this.w.compareTo(o.w);
        }
    }
    public int findString(String[] words, String s) {
        List<Word> ws = new ArrayList<>();
        for(int i = 0; i < words.length; i++) {
            if(!"".equals(words[i])) {
                ws.add(new Word(words[i], i));
            }
        }
        int index = Collections.binarySearch(ws, new Word(s, -1), new Comparator<Word>() {
            @Override
            public int compare(Word o1, Word o2) {
                return o1.compareTo(o2);
            }
        });
        return index < 0? -1 : ws.get(index).index;
    }

    //二分
    private int res = -1;
    public int findString2(String[] words, String s) {
        partition(words,s,0,words.length-1);
        return res;
    }
    private void partition(String[] words, String s, int start, int end){
        if(start>end) return;
        int mid = start + (end - start)/2;
        if(words[mid].equals(s)){
            res = mid;
            return;
        }
        partition(words,s,start,mid-1);
        if(res == -1) partition(words,s,mid+1,end);

    }
}
